package ua.yandex.collections;

import java.util.Comparator;

public class MyCollections {

    // Reverses the order of the elements in the specified list
    public static void reverse(MyList list) {
        Object[] listToArray;
        Object Y;
        listToArray = list.toArray();
        for (int i = 0; i < list.size()/2; i++) {
            Y = listToArray[i];
            listToArray[i] = listToArray[list.size() - i - 1];
            listToArray[list.size() - i - 1] = Y;
        }
        list.clear();
        list.addAll(listToArray);
    }
    
    //Реализует рекурсивный поиск в отсортированном массиве методом бисекции.
    public static int binarySearch(MyList list, Object key) {
        //Если элемент найден, то возвращается его индекс. 
        //Если не найдет, то возвращается отрицательное значение, 
        //вычисляемое по следующей формуле: 
        //(-(insertion point) - 1), где insertion point - индекс того места 
        //в массиве, где должен был бы быть указанный элемент.
        if(list.isEmpty()) {
            return -0 - 1;
        }
        int a = -1, b = list.size();
        
        return binarySearch(list, key, a, b);
    }

    private static int binarySearch(MyList list, Object key, int a, int b) {
        int c;
        if (b - a > 1) {
            c = (a + b)/2;
            if (((Comparable) key).compareTo(list.get(c)) < 0) {
                b = c;
            }
            else if (((Comparable) key).compareTo(list.get(c)) > 0) {
                a = c;
            }
            else {
                return c;
            }
        }
        else return -(a + 2);
        return binarySearch(list, key, a, b);
    }
    
    //Реализует нерекурсивный поиск в отсортированном массиве методом бисекции.
    public static int binarySearch(MyList list, Object key, Comparator cp) {
        int a, b, c = 0;
        a = -1;
        b = list.size();
        while (b - a > 1) {
            c = (a + b)/2;
            if (cp.compare(key, list.get(c)) < 0) {
                b = c;
            }
            else if (cp.compare(key, list.get(c)) > 0) {
                a = c;
            }
            else {
                return c;
            }
        }
        return -(a + 2);
    }
}